import heapq
class Solution:
    def numberOfSets(self, n: int, maxDistance: int, roads) -> int:
        d = [[10 ** 5 + 1 for _ in range(n)] for _ in range(n)]
        for u, v, c in roads:
            d[u][v] = min(d[u][v], c)
            d[v][u] = min(d[v][u], c)
        def find(val):
            st = []
            for i in range(n):
                if (val >> i) & 1:
                    st.append(i)
            for u in st:
                dis = []
                already = {u: 0}
                for v in st:
                    if v != u:
                        heapq.heappush(dis, [d[u][v], v])
                while dis:
                    dis_value, node = heapq.heappop(dis)
                    if node not in already:
                        already[node] = dis_value
                        for v in st:
                            if v not in already:
                                heapq.heappush(dis, [d[node][v] + already[node], v])
                if max(already.values()) > maxDistance:
                    return False
            return True
        ans = 0
        for val in range(2 ** n):
            if find(val):
                ans += 1
        return ans

data = Solution()
n = 3
maxDistance = 5
roads = [[0,1,20],[0,1,10],[1,2,2],[0,2,2]]
print(data.numberOfSets(n, maxDistance, roads))



